package com.LeeCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 二叉树最大宽度
 */

public class Code662 {
    public static void main(String[] args) {
        Integer[] arr = {1, 3, 2, 5, null, null, 9, 6, null, 7};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code662().widthOfBinaryTree(root));
    }

    public int widthOfBinaryTree(TreeNode root) {
        Deque<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(root, 0));
        int width = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            int left = 0, right = 0;
            int minIdex = queue.peek().index;
            for (int i = 0; i < size; i++) {
                Pair pair = queue.poll();
                TreeNode node = pair.node;
                int index = pair.index - minIdex;
                if (i == 0) left = pair.index;
                if (i == size - 1) right = pair.index;
                if (node.left != null)
                    queue.offer(new Pair(node.left, 2 * index + 1));
                if (node.right != null)
                    queue.offer(new Pair(node.right, 2 * index + 2));
            }
            width = Math.max(width, right - left + 1);
        }
        return width;
    }

    class Pair {
        public TreeNode node;
        public int index;

        public Pair(TreeNode node, int index) {
            this.node = node;
            this.index = index;
        }
    }
}
